package LeetCode.Leet500_599.Leet510_519.Leet518;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/9/21 15:45
 * @Description TODO: 方法一   动态规划    3ms 100%
 */
class Solution_1 {
    public int change(int amount, int[] coins) {
        // 完全背包问题（动态规划）
        // 第i次循环，dp[j]表示前i种银币组成金额j的组合数
        int[] dp = new int[amount + 1];
        // 默认组成金额0存在一种情况，就是为空，同时可以确保动态规划不丢失情况
        dp[0] = 1;
        for(int i = 0;i < coins.length;i++){
            int money = coins[i];
            for(int j = money;j <= amount;j++){
                // 面额不低于目标金额，则两种情况取和：
                // 1.加入当前面额，即dp[j - money]种情况
                // 2.不加当前面额，即dp[j]种情况
                // 前面dp[0]初始化为1，可以确保当硬money等于j时，会记录上新的情况，就是一个硬币凑出答案的情况
                dp[j] = dp[j] + dp[j - money];
                // 若面额低于目标金额，则保持不变（也就是不加入金额money），不需要代码所以循环面额从目标金额开始

            }
        }
        return dp[amount];
    }
}
